package leetcode.day_2021_03_22_2021_03_28;

/**
 * 69. x 的平方根
 * https://leetcode-cn.com/problems/sqrtx/
 * https://leetcode-cn.com/problems/sqrtx/solution/er-fen-cha-zhao-niu-dun-fa-python-dai-ma-by-liweiw/
 */
public class LeetCode0069 {

    public static int mySqrt(int x) {
        int left = 0;
        int right = x/2 + 1;
        while (left <= right) {
            int mid = left + (right - left)/2;
            if (Math.pow(mid, 2) > x) {
                right = mid-1;
            } else {
                left = mid+1;
            }
        }
        return left-1;
    }

    public static int mySqrt2(int a) {
        long x = a;
        while (x*x > a) {
            x = (x + a/x) / 2;
        }
        return  (int) x;
    }

    public static void main(String[] args) {
        System.out.println(mySqrt2(2147395599));
    }
}
